class Solution {
public:
	static const int N = 1e5 + 10, M = N * 2;
	int h[N], e[M], ne[M], idx;
	int f[N];
	int low[N], dfn[N], stk[N], top, timestamp;
	int scc_cnt, id[N], sz[N];
	int din[N], dout[N];
	bool in_stk[N];
	int n;
	void add(int a, int b)
	{
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	}
	void tarjan(int u)
	{
		low[u] = dfn[u] = ++timestamp;
		stk[++top] = u, in_stk[u] = 1;
		for (int i = h[u]; ~i; i = ne[i]) {
			int j = e[i];
			if (!dfn[j]) {
				tarjan(j);
				low[u] = min(low[u], low[j]);
			}
			else if (in_stk[j]) {
				low[u] = min(low[u], dfn[j]);
			}
		}
		if (dfn[u] == low[n]) {
			++scc_cnt;
			int y;
			do {
				y = stk[top--];
				in_stk[y] = 0;
				id[y] = scc_cnt;
				sz[scc_cnt] ++;
			} while (y != u);
		}
	}
	int dfs(int u)
	{
		if (f[u])return f[u];
		int res = sz[u];
		for (int i = h[u]; ~i; i = ne[i]) {
			int j = e[i];
			res+=dfs(j);
		}
		f[u] = res;
		return f[u];
	}
	vector<int> countVisitedNodes(vector<int>& edges) {
		n = edges.size();
		memset(h, -1, sizeof(h));
		for (int i = 0; i < n; i++) {
			add(i + 1, edges[i] + 1);
		}
		for (int i = 1; i <= n; i++) {
			if (!dfn[i]) {
				tarjan(i);
			}
		}
		idx = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = h[i]; ~j; j = ne[j]) {
				int k = e[j];
				if (id[i] != id[k]) {
					add(id[i], id[k]);
				}
			}
		}
		vector<int>ans;
		for (int i = 1; i <= n; i++) {
			int res = dfs(id[i]);
			ans.push_back(res);
		}
		return ans;
	}
};
